package fr.cephb.util;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.util.Comparator;
import java.util.Random;

public class FQuickSort
	{
	private Comparator<byte[]> comparator;
	private int sizeof;
	private byte swap_array_1[]=null;
	private byte swap_array_2[]=null;
	private byte cmp_array_1[]=null;
	private byte cmp_array_2[]=null;
	
	public FQuickSort(int sizeof,Comparator<byte[]> comparator)
		{
		if(sizeof<=0) throw new IllegalArgumentException("Bad sizeof:"+sizeof);
		this.sizeof=sizeof;
		this.comparator=comparator;
		this.swap_array_1=new byte[sizeof];
		this.swap_array_2=new byte[sizeof];
		this.cmp_array_1=new byte[sizeof];
		this.cmp_array_2=new byte[sizeof];
		}
	
	public FQuickSort(int sizeof)
		{
		this(sizeof,null);
		}
	
	
	private void exchange(RandomAccessFile buffer,long i, long j)
		throws IOException
		{
		fullyRead(buffer, i*sizeof, this.swap_array_1);
		fullyRead(buffer, j*sizeof, this.swap_array_2);
		buffer.seek(j*sizeof);
		buffer.write(this.swap_array_1);
		buffer.seek(i*sizeof);
		buffer.write(this.swap_array_2);
		}
	
	private void fullyRead(RandomAccessFile in, long seekPos,byte array[])
		throws IOException
		{
		in.seek(seekPos);
		in.readFully(array);
		}
	
	private int compare(
		RandomAccessFile buffer,
		final long index1,
		final long index2)
		throws IOException
		{
		fullyRead(buffer,index1*sizeof,this.cmp_array_1);
		fullyRead(buffer,index2*sizeof,this.cmp_array_2);
		
		if(this.comparator!=null)
			{
			return comparator.compare(
				this.cmp_array_1,
				this.cmp_array_2
				);
			}
		
		for(int i=0;i<sizeof;++i)
			{
			int a=this.cmp_array_1[i];
			int b=this.cmp_array_2[i];
			if(a!=b)
				{
				return a-b;
				}
			}
		return 0;
		}

	private void shuffle(RandomAccessFile io)
		throws IOException
		 {
		 Random rand= new Random();
	     int N = (int)(io.length()/sizeof);
	     for (int i = 0; i < N; i++)
	    	 {
	    	 int r = i + rand.nextInt(N-i);   // between i and N-1
	         exchange(io, i, r);
	     	}
    	}	
	
	
	public void sort(File file) throws IOException
		{
		if(!file.exists()) throw new FileNotFoundException(file.toString());
		if(!file.isFile()) throw new IOException("Not a file: "+file.toString());
		long file_length=file.length();
		if(file_length%this.sizeof!=0)
			{
			throw new IOException("bad file size "+file_length+"%"+sizeof+"!=0");
			}
		RandomAccessFile io=new RandomAccessFile(file, "rw");
		shuffle(io);
		quicksort(io,0,(file_length/sizeof)-1);
		io.close();
		}
	
	private void quicksort(RandomAccessFile io,final long low,final long high)
		throws IOException
		{
		if(high<=low) return;
		long i= partition(io,low,high);
		quicksort(io,low,i-1);
		quicksort(io,i+1,high);
		}
	
	 private long partition(RandomAccessFile a, long left, long right)
	 	throws IOException
		 {
		 long i = left - 1;
		 long j = right;
	     while (true)
	    	 {
	         while(compare(a,++i, right)<0)      // find item on left to swap
	             {                               // a[right] acts as sentinel
	             //nothing
	             }
	         while (compare(a,right,--j)<0)      // find item on right to swap
	             {
	             if (j == left) break;           // don't go out-of-bounds
	             }
	         if (i >= j) break;                  // check if pointers cross
	        exchange (a, i, j);                      // swap two elements into place
	     	}
	     exchange(a, i, right);                      // swap with partition element
	     return i;
		 }
	private void echo(File f)
		throws IOException
		{
		RandomAccessFile in=new RandomAccessFile(f, "r");
		byte buff[]=new byte[this.sizeof];
		for(int i=0;i< 100;++i)
			{
			in.seek(i*sizeof);
			in.readFully(buff);
			System.err.println(new String(buff));
			}
		
		in.close();
		}
	public static void main(String[] args)
		throws Exception
		{
		File f=new File("/home/pierre/jeter.bin");//File.createTempFile("_qsort", ".bin");
		//f.deleteOnExit();
		Random rand= new Random();
		
		
		RandomAccessFile out=new RandomAccessFile(f, "rw");
		for(int i=0;i< 100;i++)
			{
			StringBuilder b= new StringBuilder();
			for(int j=0;j<9;++j)
				{
				b.append((char)('A'+rand.nextInt(26)));
				}
			b.append('.');
			out.write(b.toString().getBytes());
			}
		
		out.close();
		FQuickSort q= new FQuickSort(10);
		q.echo(f);
		System.err.println("Sort...");
		q.sort(f);
		//q.echo(f);
		q= new FQuickSort(10,new Comparator<byte[]>()
			{
			@Override
			public int compare(byte[] o1, byte[] o2)
				{
				return new String(o2).compareToIgnoreCase(new String(o1));
				}
			});
		q.sort(f);
		q.echo(f);
		f.delete();
		}
	
	}
